import { MaxPQ } from "./interfaces/MaxPQ"
import { HeapComparable } from "./interfaces/HeapComparable";
import { randomInt } from "../common/Calculate";

class PriorityQueue<T extends HeapComparable<T>> implements MaxPQ<T> {
    arr: T[];
    len: number;
    copyTimes: number;
    COPY_OFFSET = 10;
    constructor(capacity: number) {
        this.arr = new Array<T>(capacity + 5);
        this.len = 1;
        this.copyTimes = 1;
    }
    public insert(val: T): boolean {
        if (this.len >= this.arr.length) {
            this.arr = this.copyArray(this.arr, this.arr.length + this.COPY_OFFSET * this.copyTimes);
        }
        this.arr[this.len] = val;
        this.swim(val);
        return true;
    }
    public size(): number {
        return this.len - 1;
    }
    public isEmpty(): boolean {
        if (this.size() == 0) {
            return true;
        } else {
            return false;
        }
    }
    public max(): T | any {
        if (this.isEmpty()) {
            return null;
        } else {
            return this.arr[1];
        }
    }
    public delMax(): T | any {
        if (this.isEmpty()) {
            return null;
        }
        return this.sink();
    }

    private getFather(index: number): number {
        return Math.floor(index / 2);
    }

    private getLeftChild(index: number): number {
        return index * 2;
    }

    private getRightChild(index: number): number {
        return index * 2 + 1;
    }

    private copyArray(arr: Array<T>, newLen: number): Array<T> {
        let newArr: Array<T> = new Array<T>(newLen);
        for (let i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        return newArr;
    }

    private swim(val: T) {
        //将弹出的宫女 设置到相应位置
        val.setXPx(this.getXByIndex(this.len))
        val.setYPx(this.getYByIndex(this.len))
        let subIndex: number = this.len;
        let fatherIndex: number = this.getFather(subIndex);
        //父节点没有出界
        while (fatherIndex != 0 && this.arr[subIndex].compare(this.arr[fatherIndex])) {
            //记录交换父子结点的坐标信息
            let ypx_father = this.arr[fatherIndex].getYPx();
            let xpx_father = this.arr[fatherIndex].getXPx();
            let ypx_son = this.arr[subIndex].getYPx();
            let xpx_son = this.arr[subIndex].getXPx();
            console.log("RECORD:", xpx_father, ypx_father, xpx_son, ypx_son);
            //交换父子结点在数组中的引用 但他们的坐标信息尚未更新
            let temp: T = this.arr[fatherIndex];
            this.arr[fatherIndex] = this.arr[subIndex];
            this.arr[subIndex] = temp;
            //重设交换后，父子结点的坐标 因为子结点是之前的父节点，它的坐标信息尚未更新
            this.arr[fatherIndex].setXPx(xpx_father);
            this.arr[fatherIndex].setYPx(ypx_father);
            this.arr[subIndex].setXPx(xpx_son)
            this.arr[subIndex].setYPx(ypx_son)
            console.log("REFRESH", this.arr[fatherIndex].getXPx(), this.arr[fatherIndex].getYPx(), this.arr[subIndex].getXPx(), this.arr[subIndex].getYPx());
            //更新父节点与子结点
            subIndex = fatherIndex;
            fatherIndex = this.getFather(fatherIndex);
        }
        this.len++;
        console.log("DEBUG");
        for (let i = 1; i < this.len; ++i) {
            console.log(this.arr[i]);
        }
    }
    getYByIndex(index: number): string {
        let layer = Math.floor(Math.log2(index));
        let offset: number = 20;
        let layerOffset: number = 80;
        offset = offset + layer * layerOffset;
        return offset + "px"
    }
    getXByIndex(index: number): string {
        let layer = Math.floor(Math.log2(index));
        const basicOffset = 720;
        const basicUnitSpan = 40;
        const layerUnitXSpan: number = basicUnitSpan * Math.pow(2, (3 - layer));
        let x = index - Math.pow(2, layer);
        return (basicOffset + layerUnitXSpan + 2 * layerUnitXSpan * x) + "px";
    }

    private sink(): T | any {
        let popValue: T = this.arr[1];
        this.arr[1] = this.arr[this.len - 1];
        //将弹出的宫女设置到地图的左边
        popValue.setXPx(this.generateFeiziX())
        popValue.setYPx(this.generateFeiziY())
        this.len--;
        let sinkIndex: number = 1;
        //sinkindex对应的元素需要马上重置一次位置
        this.arr[sinkIndex].setXPx(this.getXByIndex(sinkIndex))
        this.arr[sinkIndex].setYPx(this.getYByIndex(sinkIndex))
        while (true) {
            let leftIndex: number = this.getLeftChild(sinkIndex);
            let rightIndex: number = this.getRightChild(sinkIndex);
            let newSinkIndex: number;
            if (leftIndex < this.len && rightIndex < this.len) {
                if (this.arr[leftIndex].compare(this.arr[rightIndex])) {
                    newSinkIndex = leftIndex;
                } else {
                    newSinkIndex = rightIndex;
                }
            } else if (leftIndex < this.len) {
                newSinkIndex = leftIndex;
            } else {
                break
            }
            if (this.arr[newSinkIndex].compare(this.arr[sinkIndex])) {
                //记录下坐标信息
                let x_sink = this.arr[sinkIndex].getXPx();
                let y_sink = this.arr[sinkIndex].getYPx();
                let x_newsink = this.arr[newSinkIndex].getXPx();
                let y_newsink = this.arr[newSinkIndex].getYPx();
                //交换
                let temp: T = this.arr[sinkIndex];
                this.arr[sinkIndex] = this.arr[newSinkIndex];
                this.arr[newSinkIndex] = temp;
                //坐标信息更细
                this.arr[sinkIndex].setXPx(x_sink);
                this.arr[sinkIndex].setYPx(y_sink);
                this.arr[newSinkIndex].setXPx(x_newsink);
                this.arr[newSinkIndex].setYPx(y_newsink);
                //下沉坐标更新
                sinkIndex = newSinkIndex;
            } else {
                break
            }
        }
        return popValue;
    }
    generateFeiziY(): string {
        return randomInt(20, 350) + "px";
    }
    generateFeiziX(): string {
        return randomInt(40, 450) + "px";
    }

    public getArray(): Array<T> {
        let newArr: Array<T> = new Array(this.size());
        for (let i = 0; i < this.size(); ++i) {
            newArr[i] = this.arr[i + 1];
        }
        return newArr;
    }

    /**
     * 重置新加入的元素的 位置信息
     */
    // resetElementPosition(val: Gongnv) {
    // let layer = Math.floor(Math.log2(this.len))
    // val.setXPx("550px")
    // val.setYPx("100px")
    // }
}

export { PriorityQueue }